package 搜索算法.深度优先搜索;

import java.util.ArrayList;
import java.util.List;

/**
 * 1. 问题描述
 *      给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。
 *
 * 2. 算法分析
 *      注意：此问题和排列问题之间的不同，对于排列问题，我们需要考虑元素的出现次序
 *      即每次都是从头开始搜索
 *      但是对于，组合问题，我们不需要考虑元素出现的次序，即1 2 3 和 3 2 1是等价的
 *      所以每次我们只需要从当前元素的下一位开始组合即可，就是这里和排列不同，代码大致相同
 *
 *      1. 递归+回溯   效率比较低
 *
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class 组合数组中的元素 {
    public static void main(String[] args) {

    }

    public static List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> res = new ArrayList<>(); // 记录所有结果
        List<Integer> temp = new ArrayList<>(); // 记录当前找到的组合
        boolean[] visited = new boolean[n];
        dfs(res,temp,k,0,n,visited);
        return res;
    }

    // 如何设置参数?
    // 1. 最终结果集合 2. 当前结果集合  3. 边界变量  4. 当前组合的起始元素
    // 此时我们需要使用访问数组吗? 需要 5. 访问数组
    public static void dfs(List<List<Integer>> res,List<Integer> temp,int k,int i,int n,boolean[] visited) {
        if(temp.size() == k) {
            res.add(new ArrayList<>(temp)); // 深拷贝
            return;
        }
        // 从第i个元素开始进行组合
        for(int j = i; j < n; j++) {
            if(visited[j]==false) {
                visited[j] = true;
                temp.add(j+1);
                dfs(res,temp,k,j+1,n,visited); // 递归
                visited[j] = false;  // 回溯
                temp.remove(temp.size()-1); // 回溯
            }
        }
    }
}
